This invention relates to the field of binary adders of the signal selection type.
Numerous adder architectures are used today. Three of the most popular of these architectures are the ripple adder, the carry look-ahead adder, and the carry select adder. One of the latest adder architectures is the carry multiplexed adder, which is described in the above referred-to copending patent application.
The ripple adder is the simplest adder architecture. It uses full adder cells with the carry out of one cell connected to the carry in of the next cell. It requires very few gates, but it is extremely slow, being of the order of n relationship [O(n)] between propagation delay time and number of adder cells.
The carry look-ahead adder uses combinational logic to determine propagate terms and generate terms that are used to produce the carry and sum output. The carry look-ahead adder processes data very quickly and is of time O(log.sub.2 (n)) with respect to n (the number of bits processed), but its gate growth is very high, O(n.sup.3). Carry look-ahead adders are therefore not useful for large bit applications.
The carry select adder uses parallel carry chains to produce two possible summation outputs. The correct summation is selected by the carry input to the carry select stage. The carry select adder requires about twice as many gates as the ripple adder, however, it processes numbers on the order of O(n.sup.1/2) time, which is faster than the ripple adder but not as fast as the carry look-head adder.
The carry multiplexed adder calculates four possible carry outputs with a minimal set of hardware components. It then multiplexes the carries using the carry results from previous substages and stages to determine the correct carry output. Then the carry output is used to calculate the summation output. The carry multiplexed adder requires slightly fewer gates than the carry select adder and processes n bits in order O(n.sup.1/3) time, but it is still slower than the carry look-ahead adder. The Carry Multiplexed Adder is moreover described in the above referred-to and incorporated by reference patent application of Scriber et al, herein referred to as the Scriber et al application or more simply as Scriber et al.
The high order carry multiplexed adder (HOCMA) is an extension of the carry multiplexed adder. This extension provides an adder form capable of processing addend and augend inputs of larger bit sizes while also retaining the advantages of small delay time and small circuit area requirement.
It is therefore an object of the invention to provide a desirable binary adder architecture for adders of larger bit capacity.
It is another object of the invention to provide a large bit adder architecture that is capable of desirable propagation delay time performance.
It is another object of the invention to provide a large bit adder architecture capable of fabrication within desirable circuit area requirements.
It is another object of the invention to provide an adder capable of adding two binary numbers in the time equivalent to that of a full carry look-ahead adder.
It is another object of the invention to provide a large bit adder which is characterized by a desirable delay time and circuit area performance product.
Additional objects and features of the invention will be understood from the following description and claims and the accompanying drawings.
These and other objects of the invention are achieved by high order carry multiplexed adder apparatus which includes a plurality of lower ordered adder stages each comprised of plural bit slice cells having addend, augend, and carry input signal ports and sum and carry output signals ports, the lower ordered adder stage input-ports being connected with the lowest ordered and respective successive consecutive increasing ordered bits of the addend and augend signals, the lower ordered adder stages also including second and third level substage interconnection of the bit slice cells wherein presumed zero and presumed one related carry signals are interconnected between predetermined of the bit slice cells therein resident, and a higher order adder stage connected to the next successive consecutive increasing order bits of the addend and augend signals following the lower ordered adder stages, the higher order adder stage including a group of substages having a plurality of interconnected bit slice cells wherein at least one of the interconnected cells is a fourth level cell inclusive of a next addend and augend signal connected sum signal circuit, exclusive OR, and exclusive NOR signal generating circuits and also inclusive of presumed zero and presumed one determined carry signal generating circuits and a three-leveled tree of multiplexer circuit means for selecting the correct carry signal output thereof.